The High Efficiency Video Coding (HEVC) standard is developed under the joint video project of the ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG) standardization organizations, and is especially with partnership known as the Joint Collaborative Team on Video Coding (JCT-VC).
In HEVC, one slice is partitioned into multiple coding tree units (CTU). In main profile, the minimum and the maximum sizes of CTU are specified by the syntax elements in the sequence parameter set (SPS). The allowed CTU size can be 8×8, 16×16, 32×32, or 64×64. For each slice, the CTUs within the slice are processed according to a raster scan order.
The CTU is further partitioned into multiple coding units (CU) to adapt to various local characteristics. A quadtree, denoted as the coding tree, is used to partition the CTU into multiple CUs. Let CTU size be M×M, where M is one of the values of 64, 32, or 16. The CTU can be a single CU or can be split into four smaller units of equal sizes (i.e., M/2×M/2), which are nodes of coding tree. If units are leaf nodes of coding tree, the units become CUs. Otherwise, the quadtree splitting process can be iterated until the size for a node reaches a minimum allowed CU size as specified in the SPS. This representation results in a recursive structure as specified by a coding tree (also referred to as a partition tree structure) 120 in FIG. 1. The CTU partition 110 is shown in FIG. 1, where the solid lines indicate CU boundaries. The decision whether to code a picture area using Inter-picture (temporal) or Intra-picture (spatial) prediction is made at the CU level. Since the minimum CU size can be 8×8, the minimum granularity for switching between different basic prediction types is 8×8.
One or more prediction units (PU) are specified for each CU. Coupled with the CU, the PU works as a basic representative block for sharing the prediction information. Inside each PU, the same prediction process is applied and the relevant information is transmitted to the decoder on a PU basis. A CU can be split into one, two, or four PUs according to the PU splitting type. HEVC defines eight shapes for splitting a CU into PU as shown in FIG. 2. Unlike the CU, the PU may only be split once. The partitions shown in the second row correspond to asymmetric partitions, where the two partitioned parts have different sizes.
After obtaining the residual block by applying the prediction process based on the PU splitting type, a CU can be partitioned into transform units (TUs) according to another quadtree structure, which is analogous to the coding tree for the CU. In FIG. 1, the solid lines in block 110 indicate CU boundaries, and dotted lines in block 110 indicate TU boundaries. Similarly, the solid lines for the partition tree structure 120 corresponds to the CU partition tree structure and the dashed lines for the partition tree structure 120 corresponds to the TU partition tree structure. The TU is a basic representative block of residual or transform coefficients for applying the integer transform and quantization. For each TU, one integer transform with the same size is applied to the TU to obtain residual coefficients. These coefficients are transmitted to the decoder after quantization on a TU basis.
The terms, coding tree block (CTB), coding block (CB), prediction block (PB), and transform block (TB) are defined to specify the 2-D sample array of one colour component associated with CTU, CU, PU, and TU, respectively. Thus, a CTU consists of one luma CTB, two chroma CTBs, and associated syntax elements. A similar relationship is valid for CU, PU, and TU.
The tree partitioning is generally applied simultaneously to both the luma and chroma components, although exceptions may apply when certain minimum sizes are reached for the chroma component.
However, due to some restrictions of the current HEVC block partitioning structure, the coding efficiency may not be sufficient to cope with the ever increasing demands for larger storage and transmission of video contents. The restrictions of the current HEVC block partitioning structure exist in the quadtree based partitioning from CTU to CU and from CU to TU and the limited depth of PU partitioning.
A binary tree structure has been disclosed by some common inventors for partitioning a unit into multiple smaller units, such as partitioning a slice into CTUs, a CTU into CUs, a CU into PUs, or a CU into TUs in the PCT Patent Application, No. PCT/CN2015/096761.
In the binary tree partitioning structure as disclosed in the PCT Patent Application, No. PCT/CN2015/096761, a block can be recursively split into two smaller blocks. There are various binary splitting types as shown in FIG. 3. The simplest ones are the symmetric horizontal and vertical split as shown in the top row of the splitting types in FIG. 3. Therefore, in one embodiment of the PCT Patent Application, No. PCT/CN2015/096761, only these two splitting types are used for binary splitting. For a given block of size M×N, a flag is signalled to indicate whether a block is split into two smaller blocks. If yes, another syntax element is signalled to indicate which splitting type is used. If the horizontal splitting is used then it is split into two blocks of size M×N/2. Otherwise, it is vertical split into two blocks of size M/2×N.
The binary tree splitting process can be iterated until the size (i.e., width or height) for a splitting block reaches a minimum allowed block size. The minimum allowed block size can be defined in high level syntax such as SPS (sequence parameter set). Since the binary tree has two splitting types (i.e., horizontal and vertical), the minimum allowed block width and height should be both indicated. Non-horizontal splitting is implicit when splitting would result in a block height smaller than the indicated minimum. Non-vertical splitting is implicit when splitting would result in a block width smaller than the indicated minimum. FIG. 4 illustrates an example of block partitioning 410 and its corresponding binary tree structure 420. In each splitting (i.e., non-leaf) node of the binary tree structure, one flag is used to indicate which splitting type (i.e., horizontal or vertical) is used, where 0 indicates horizontal splitting and 1 indicates vertical splitting.
The proposed binary tree structure can be used for partitioning a block into multiple smaller blocks such as partitioning a slice into CTUs, a CTU into CUs, a CU into PUs, or a CU into TUs, and so on. In one embodiment, the binary tree is used for partitioning a CTU into CUs. In other words, the root node of the binary tree is a CTU and the leaf nodes of the binary tree are CUs. The leaf nodes are further processed by prediction and transform coding. In another embodiment, there is no further partitioning from CU to PU or from CU to TU to simplify the block partitioning process. That means the CU is equal to the PU and also equal to TU. Therefore, the leaf nodes of the binary tree are also the basic unit for prediction and transform coding in this case.
The binary tree structure is more flexible than the quadtree structure, since the binary tree structure allows more partition shapes, which is also the source of coding efficiency improvement. However, the encoding complexity will also increase due to the increased selections for choosing the best partition shape. In order to balance between the complexity and coding efficiency, the PCT Patent Application, No. PCT/CN2015/096761 discloses a method to combine the quadtree and binary tree structure, which is called as quadtree plus binary tree (QTBT) structure. In an exemplary QTBT structure, a block is firstly partitioned by a quadtree structure, and the quadtree splitting can be iterated until the size for a splitting block reaches the minimum allowed quadtree leaf node size. If the leaf quadtree block is not larger than the maximum allowed binary tree root node size, it can be further partitioned by a binary tree structure. The binary tree splitting can be iterated until the size (i.e., width or height) for a splitting block reaches the minimum allowed binary tree leaf node size (i.e., width or height) or the binary tree depth reaches the maximum allowed binary tree depth.
In the QTBT structure, the minimum allowed quadtree leaf node size, the maximum allowed binary tree root node size, the minimum allowed binary tree leaf node width and height, and the maximum allowed binary tree depth can be indicated in a high level syntax such as the SPS. FIG. 5 illustrates an example of block partitioning 510 and its corresponding QTBT structure 520. The solid lines indicate quadtree splitting and dotted lines indicate binary tree splitting. In each splitting (i.e., non-leaf) node of the binary tree, one flag is signalled to indicate which splitting type (i.e., horizontal or vertical) is used, where 0 indicates horizontal splitting and 1 indicates vertical splitting.
The QTBT structure can be used for partitioning a block into multiple smaller blocks, such as partitioning a slice into CTUs, a CTU into CUs, a CU into PUs, or a CU into TUs, and so on. In one embodiment of the PCT Patent Application, No. PCT/CN2015/096761, the QTBT is used for partitioning a CTU into CUs, where the root node of the QTBT is a CTU that is partitioned into multiple CUs by a QTBT structure. The CUs are further processed by prediction and transform coding. To simplify the partition process, there is no further partitioning from CU to PU or from CU to TU. This implies that each CU is equal to a PU as well as a TU. In other words, the leaf node of the QTBT structure is the basic unit for prediction and transform.
To illustrate an example of the QTBT structure, system parameters are set as follows: a CTU with size 128×128, the allowed quadtree leaf node size equal to 16×16, the maximum allowed binary tree root node size equal to 64×64, the minimum allowed binary tree leaf node width and height both equal to 4, and the maximum allowed binary tree depth equal to 4. Firstly, the CTU is partitioned by a quadtree structure and the leaf quadtree unit may have size from 16×16 (i.e., the minimum allowed quadtree leaf node size) up to 128×128 (i.e., CTU size with no split). If the leaf quadtree unit is 128×128, it cannot be further split by binary tree since the size exceeds the maximum allowed binary tree root node size, 64×64. Otherwise, the leaf quadtree unit can be further split by binary tree, and each leaf quadtree unit is also the root binary tree unit and has binary tree depth as 0. When the binary tree depth reaches 4 (i.e., the indicated maximum), no further splitting is implicit. Accordingly, when the binary tree node has width equal to 4, non-horizontal splitting is implicit, and when the binary tree node has height equal to 4, non-vertical splitting is implicit. The leaf nodes of the QTBT are further processed by prediction (e.g. Intra-picture or Inter-picture prediction) and transform coding.
The tree structure is applied separately to luma and chroma for I slice, and applied simultaneously to both luma and chroma for P- and B-slice except when certain minimum sizes are reached for the chroma component. In other words, in an I-slice, the luma CTB has its QTBT block partitioning, and the two chroma CTBs has another QTBT block partitioning. However, the two chroma CTBs can also have their own QTBT block partitioning.
While the QTBT structure provides more flexibility, it may introduce some redundant structures. FIG. 6A through FIG. 6C illustrate examples of redundant structures. In FIG. 6A, a block is split into 4 sub-blocks directly using quad-partition. In FIG. 6B, a block is split into an above block and a below block using horizontal binary partition, and each block is further split into a left block and a right block using vertical binary partition. In FIG. 6C, a block is split into a left block and a right block using vertical binary partition, and each block is further split into an above block and a below block using horizontal binary partition. All splitting paths in FIG. 6A through FIG. 6C result in the same partitions, i.e., four sub-blocks.